package bma.common.langutil.concurrent;

import java.util.Collection;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;

/**
 * 哈希时间轮盘数据对象
 * 
 * @author 关中
 * @since 1.0 (imported from BMA.ESP Project)
 * 
 */
public class HashedTimeWheel {

	public static class HashedTimeWheelItemComparator implements
			Comparator<HashedTimeWheelItem> {
		@Override
		public int compare(HashedTimeWheelItem o1, HashedTimeWheelItem o2) {
			if (o1 == o2)
				return 0;
			long t1 = o1.getTime();
			long t2 = o2.getTime();
			if (t1 == t2)
				return 0;
			return t1 < t2 ? -1 : 1;
		}
	}

	private transient final long roundDuration;
	private final long tickDuration;
	private transient final List<HashedTimeWheelItem>[] wheel;

	/**
	 * Creates a new timer with the default thread factory (
	 * {@link Executors#defaultThreadFactory()}), default tick duration, and
	 * default number of ticks per wheel.
	 */
	public HashedTimeWheel() {
		this(100, TimeUnit.MILLISECONDS);
	}

	/**
	 * Creates a new timer with the default thread factory (
	 * {@link Executors#defaultThreadFactory()}) and default number of ticks per
	 * wheel.
	 * 
	 * @param tickDuration
	 *            the duration between tick
	 * @param unit
	 *            the time unit of the {@code tickDuration}
	 */
	public HashedTimeWheel(long tickDuration, TimeUnit unit) {
		this(tickDuration, unit, 512);
	}

	/**
	 * Creates a new timer with the default thread factory (
	 * {@link Executors#defaultThreadFactory()}).
	 * 
	 * @param tickDuration
	 *            the duration between tick
	 * @param unit
	 *            the time unit of the {@code tickDuration}
	 * @param ticksPerWheel
	 *            the size of the wheel
	 */
	public HashedTimeWheel(long tickDuration, TimeUnit unit, int ticksPerWheel) {
		if (unit == null) {
			throw new NullPointerException("unit");
		}
		if (tickDuration <= 0) {
			throw new IllegalArgumentException(
					"tickDuration must be greater than 0: " + tickDuration);
		}
		if (ticksPerWheel <= 0) {
			throw new IllegalArgumentException(
					"ticksPerWheel must be greater than 0: " + ticksPerWheel);
		}

		// Normalize ticksPerWheel to power of two and initialize the wheel.
		wheel = createWheel(ticksPerWheel);
		// mask = wheel.length - 1;

		// Convert tickDuration to milliseconds.
		this.tickDuration = tickDuration = unit.toMillis(tickDuration);

		// Prevent overflow.
		if (tickDuration == Long.MAX_VALUE
				|| tickDuration >= Long.MAX_VALUE / wheel.length) {
			throw new IllegalArgumentException("tickDuration is too long: "
					+ tickDuration + ' ' + unit);
		}

		roundDuration = tickDuration * wheel.length;
	}

	public long getRoundDuration() {
		return roundDuration;
	}

	public long getTickDuration() {
		return tickDuration;
	}

	@SuppressWarnings("unchecked")
	private static List<HashedTimeWheelItem>[] createWheel(int ticksPerWheel) {
		if (ticksPerWheel <= 0) {
			throw new IllegalArgumentException(
					"ticksPerWheel must be greater than 0: " + ticksPerWheel);
		}
		if (ticksPerWheel > 1073741824) {
			throw new IllegalArgumentException(
					"ticksPerWheel may not be greater than 2^30: "
							+ ticksPerWheel);
		}

		ticksPerWheel = normalizeTicksPerWheel(ticksPerWheel);
		List<HashedTimeWheelItem>[] wheel = new List[ticksPerWheel];
		for (int i = 0; i < wheel.length; i++) {
			wheel[i] = new LinkedList<HashedTimeWheelItem>();
		}
		return wheel;
	}

	private static int normalizeTicksPerWheel(int ticksPerWheel) {
		int normalizedTicksPerWheel = 1;
		while (normalizedTicksPerWheel < ticksPerWheel) {
			normalizedTicksPerWheel <<= 1;
		}
		return normalizedTicksPerWheel;
	}

	public int getTimeIndex(long time) {
		final long lastRoundDelay = time % roundDuration;
		final long relativeIndex = lastRoundDelay / tickDuration;
		return (int) relativeIndex;
	}

	public long nextTimeTick(long time) {
		final long lastTickDelay = time % tickDuration;
		return time - lastTickDelay + tickDuration;
	}

	public void add(HashedTimeWheelItem item) {
		long time = item.getTime();
		// Add timeout to the wheel.
		int idx = getTimeIndex(time);
		wheel[idx].add(item);
	}

	public boolean remove(HashedTimeWheelItem item) {
		long time = item.getTime();
		int idx = getTimeIndex(time);
		return wheel[idx].remove(item);
	}

	public long getMinTime(long time) {
		int idx = getTimeIndex(time);
		long ntime = nextTimeTick(time);
		Iterator<HashedTimeWheelItem> i = wheel[idx].iterator();
		while (i.hasNext()) {
			HashedTimeWheelItem item = i.next();
			if (item.isCancel()) {
				i.remove();
				continue;
			}
			if (item.getTime() < ntime) {
				ntime = item.getTime();
			}
		}
		return ntime;
	}

	public long processTickItems(long time,
			Collection<HashedTimeWheelItem> items) {
		int idx = getTimeIndex(time);
		long ntime = nextTimeTick(time);
		Iterator<HashedTimeWheelItem> i = wheel[idx].iterator();
		while (i.hasNext()) {
			HashedTimeWheelItem item = i.next();
			if (item.isCancel() || item.getTime() <= ntime) {
				i.remove();
				items.add(item);
			}
		}
		return ntime;
	}

	public int fetchExpiredItems(long time,
			Collection<HashedTimeWheelItem> expiredItems) {
		int idx = getTimeIndex(time);
		int r = 0;
		Iterator<HashedTimeWheelItem> i = wheel[idx].iterator();
		while (i.hasNext()) {
			HashedTimeWheelItem item = i.next();
			if (item.isCancel() || item.getTime() <= time) {
				i.remove();
				expiredItems.add(item);
				r++;
			}
		}
		return r;
	}

	public void clear(List<HashedTimeWheelItem> remainItems) {
		for (int i = 0; i < wheel.length; i++) {
			if (remainItems != null) {
				remainItems.addAll(wheel[i]);
			}
			wheel[i].clear();
		}
	}

}
